{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 21.4 Analysis of union by rank with path compression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.4-1\n",
    "\n",
    "> Prove Lemma 21.4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obviously."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.4-2\n",
    "\n",
    "> Prove that every node has rank at most $\\lfloor \\lg n\\rfloor$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The rank increases by 1 only when $x.rank = y.rank$, thus each time we need the twice number of elements to increase the rank by 1, therefore the rank is at most $\\lfloor \\lg n \\rfloor$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.4-3\n",
    "\n",
    "> In light of Exercise 21.4-2, how many bits are necessary to store $x.rank$ for each node $x$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\lceil \\lfloor \\lg n \\rfloor \\rceil$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.4-4\n",
    "\n",
    "> Using Exercise 21.4-2, give a simple proof that operations on a disjoint-set forest with union by rank but without path compression run in $O(m\\lg n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O((m - x) \\cdot \\lfloor \\lg n \\rfloor) = O(m \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.4-5\n",
    "\n",
    "> Professor Dante reasons that because node ranks increase strictly along a simple path to the root, node levels must monotonically increase along the path. In other words, if $x.rank > 0$ and $x.p$ is not a root, then level($x$) $\\le$ level$(x.p)$. Is the professor correct?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No. Think about an extreme condition $100 \\rightarrow 99 \\rightarrow 1$, since level$(99) = 0$, level$(1) \\ge 1$, we have level$(x)$ $>$ level$(x.p)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.4-6 $\\star$\n",
    "\n",
    "> Consider the function $\\alpha'(n) = \\min \\{k: A_k(1) \\ge \\lg(n + 1)\\}$. Show that $\\alpha'(n) \\le 3$ for all practical values of $n$ and, using Exercise 21.4-2, show how to modify the potential-function argument to prove that we can perform a sequence of $m$ MAKESET, UNION, and FIND-SET operations, $n$ of which are MAKE-SET operations, on a disjoint-set forest with union by rank and path compression in worst-case time $O(m \\alpha'(n))$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
